﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;

#include <iostream>
#include <vector>
using namespace std;
//合唱团(动态规划学习)
//https://www.nowcoder.com/questionTerminal/661c49118ca241909add3a11c96408c8
//int main()
//{
//	int n = 0; //人数
//	cin >> n;
//	vector<int> v(n); //每个人能力值表
//	for (auto& num : v) cin >> num;
//
//	int k = 0; //选择同学最大个数
//	int d = 0; //编号差距
//	cin >> k >> d;
//
//	//max[i][k] 表示以第i个同学结尾选择k个人的最大能力值
//	vector<vector<long long>> maxvv(n, vector<long long>(k, 0));
//	//min[i][k] 表示以第i个同学结尾选择k个人的最小能力值 - 防止负数和负数得最大值的情况
//	vector<vector<long long>> minvv(n, vector<long long>(k, 0));
//
//	//初始化1个人时 的能力值
//	for (int i = 0; i < n; ++i)
//		maxvv[i][0] = minvv[i][0] = v[i];
//
//	long long maxret = maxvv[0][0];
//
//	//第几个人为结尾
//	for (int i = 0; i < n; ++i)
//	{
//		//选择了几个人 0代表一个人 1代表两个人 因为初始化已经初始化过选择一个人 所以从选2个人开始
//		for (int j = 1; j < k; ++j)
//		{
//			//从第一个人遍历到第i个人(且编号差距不能超过d) 第一个人和第i个人的编号差距不能超过d 如果d>n 则从第一个人开始
//			for (int t = max(0, i - d)/*从最大差距开始到第i-1个人*/; t < i; ++t)
//			{
//				//maxvv[i][k]表示当前的默认值 maxvv[t][j - 1]*v[i]表示选择第t个人时选择j-1个人的能力值和当前位置v[i]的能力乘积 
//				//考虑到负数 负负得正也可以得最大值
//				maxvv[i][j] = max(maxvv[i][j], max(maxvv[t][j - 1] * v[i], minvv[t][j - 1] * v[i]));
//				minvv[i][j] = min(minvv[i][j], min(maxvv[t][j - 1] * v[i], minvv[t][j - 1] * v[i]));
//			}
//		}
//		maxret = max(maxvv[i][k - 1], maxret); //记录最大值(选择k个人时的最大值-最大人数)
//	}
//
//	cout << maxret << endl;
//	return 0;
//}

//马戏团(动态规划学习)
//https://www.nowcoder.com/questionTerminal/c2afcd7353f84690bb73aa6123548770
//struct people //每个人的信息
//{
//    int _h; //身高
//    int _w; //体重
//
//    //比较函数 方便排序 以体重排序 如果体重相等或小于而身高大于则是false 如果体重小于或体重相等身高小于则是true
//    bool operator<(const people& obj)
//    {
//        if (_w != obj._w) return _w <= obj._w;
//        else return _h > obj._h;
//    }
//};
//
//int main() {
//    int n = 0;
//    vector<people> vp;
//    while (cin >> n) {
//        vp.resize(n);
//        int num = 0; //编号 不需要记录
//
//        //输入数据
//        for (int i = 0; i < n; ++i) cin >> num >> vp[i]._w >> vp[i]._h;
//
//        //按体重排升序 体重相同按身高排
//        sort(vp.begin(), vp.end());
//
//        //转化为上升子序列问题
//        //初始化 默认为一个人叠罗汉
//        vector<int> v(n, 1);
//        int maxret = 0;
//        //从第2个人开始 和第一个人对比 是否可以叠起罗汉
//        for (int i = 1; i < n; ++i)//选择第i个人时可以叠的最高人数
//        {
//            //对比i前面的所有人 找出可以组队的最大叠罗汉人数
//            for (int k = 0; k < i; ++k)//遍历i前面的所有人 找到可以叠的最大人数的上一个
//            {
//                //对比两人身高(因为体重已经排过序，身高满足则完全满足) 
//                //此时对比自己当前的最大人数和该人数+1的两者最大值
//                //v[i]的人在下 v[k]的人站在v[i]人身上
//                if (vp[i]._h >= vp[k]._h) v[i] = max(v[i], v[k] + 1);
//            }
//            maxret = max(v[i], maxret);
//        }
//        cout << maxret << endl;
//    }
//    return 0;
//}